//
// Created by xux on 2024/9/24.
//
#include <cassert>
#include <cstring>
#include "Heap.h"

void Heap::shiftdown(int index) {
    int left = index<<1|1;
    int fa = index;
    while (left < size) {
        if (left+1 < size && scores[left+1] > scores[left]){
            left++;
        }
        if (scores[fa] >= scores[left]) break;
        swap(fa, left);
        fa = left;
        left = fa<<1|1;
    }
}

void Heap::shiftup(int index) {
    int fa = (index-1)>>1;
    int child = index;
    while (child && scores[fa] < scores[child]) {
        swap(child, fa);
        child = fa;
        fa = (fa-1)>>1;
    }
}

bool Heap::empty() {
    return size == 0;
}

void Heap::insert(double score, int value) {
    args[size] = value;
    arg2id[value] = size;
    scores[size++] = score;
    shiftup(size-1);
}

void Heap::pop() {
    swap(0, --size);
    shiftdown(0);
}

void Heap::remove(int arg) {
    assert(in_heap(arg));
    int id = arg2id[arg];
    if (id != 0) {
        scores[id] = MAX_SCORE;
        swap(0, id);
        shiftup(id);
    }
    pop();
}

Heap::Heap(int capacity):capacity(capacity), size(0) {
    args = new int[capacity];
    scores = new double[capacity];
    arg2id = new int[capacity];
    memset(arg2id, 0x3f, capacity * sizeof(int));
}

Heap::~Heap() {
    delete []args;
    delete []arg2id;
    delete []scores;
}

void Heap::swap(int index1, int index2) {
    std::swap(arg2id[args[index1]], arg2id[args[index2]]);
    std::swap(args[index1], args[index2]);
    std::swap(scores[index1], scores[index2]);
}

int Heap::top() {
    return args[0];
}

void Heap::update_score(double new_score, int arg) {
    assert(in_heap(arg));
    int id = arg2id[arg];
    assert(scores[id] < new_score);
    if (scores[id] < new_score){
        scores[id] = new_score;
        shiftup(id);
    }
    else if(new_score < scores[id]){
        scores[id] = new_score;
        shiftdown(id);
    }
}

bool Heap::in_heap(int arg) {
    return arg2id[arg] < size;
}

void Heap::update_all(std::vector<double> arg_scores) {
    for(int i=0;i<size;i++){
        scores[i] = arg_scores[args[i]];
    }
    for(int i=size-1;i>=0;i--){
        shiftdown(i);
    }
}



